/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/sliding-window-median
   @Language: C++
   @Datetime: 17-04-18 17:51
   */

class Solution {
public:
	/**
	 * @param nums: A list of integers.
	 * @return: The median of the element inside the window at each moving
	 */
	vector<int> medianSlidingWindow(vector<int> &nums, int k) {
		// write your code here
		multiset<int,greater<int> > maxs;
		multiset<int,less<int> > mins;
		vector<int> ans;
		for(int i=0; i<nums.size(); ++i){
			if (i>=k){      // remove i-k th element
				if (maxs.count(nums[i-k]))
					maxs.erase(maxs.find(nums[i-k]));
				else mins.erase(mins.find(nums[i-k]));
			}
			// add i-th element
			if (mins.size() && *mins.begin()>nums[i]){
				maxs.insert(nums[i]);
				if (mins.size()<maxs.size()){
					mins.insert(*maxs.begin());
					maxs.erase(maxs.begin());
				}
			}
			else{
				mins.insert(nums[i]);
				if (mins.size()>maxs.size()+1){
					maxs.insert(*mins.begin());
					mins.erase(mins.begin());
				}
			}
			if (mins.size()+maxs.size()==k)
				ans.push_back(k&1?*mins.begin():*maxs.begin());
		}
		return ans;
	}
};
